// LeetCode 主站 Problem Nr. 322: 零钱兑换

/*
给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。
计算并返回可以凑成总金额所需的 最少的硬币个数 。
如果没有任何一种硬币组合能组成总金额，返回 -1 。

你可以认为每种硬币的数量是无限的。

示例 1：
	输入：coins = [1, 2, 5], amount = 11
	输出：3
	解释：11 = 5 + 5 + 1
示例 2：
	输入：coins = [2], amount = 3
	输出：-1
示例 3：
	输入：coins = [1], amount = 0
	输出：0

提示：
    1 <= coins.length <= 12
    1 <= coins[i] <= 231 - 1
    0 <= amount <= 104

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/coin-change
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*/

package main

import "fmt"

func coinChange(coins []int, amount int) int {
	return method1(coins, amount)
}

func method1(coins []int, amount int) int {
	if amount == 0 {
		return 0
	}

	queue := []int{0}
	visited := make(map[int]bool)
	count := 0
	for len(queue) > 0 {
		size := len(queue)
		count++

		for i := 0; i < size; i++ {
			e := queue[0]
			queue = queue[1:]

			for _, c := range coins {
				if e+c == amount {
					return count
				}

				if e+c < amount && !visited[e+c] {
					queue = append(queue, e+c)
					visited[e+c] = true
				}
			}
		}
	}

	return -1
}

func main() {
	fmt.Println(coinChange([]int{1,2,5}, 11))
	fmt.Println(coinChange([]int{2}, 3))
	fmt.Println(coinChange([]int{1}, 0))
}
